package cn.cxq.learning.greedy;


import java.util.Arrays;
import java.util.Scanner;

/**
 * 链接：https://www.nowcoder.com/questionTerminal/a174820de48147d489f64103af152709?f=discussion
 * 来源：牛客网
 *
 * [编程题]分苹果
 * 热度指数：51728时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
 * 算法知识视频讲解
 * n 只奶牛坐在一排，每个奶牛拥有 ai 个苹果，现在你要在它们之间转移苹果，使得最后所有奶牛拥有的苹果数都相同，每一次，你只能从一只奶牛身上拿走恰好两个苹果到另一个奶牛上，问最少需要移动多少次可以平分苹果，如果方案不存在输出 -1。
 *
 * 输入描述:
 * 每个输入包含一个测试用例。每个测试用例的第一行包含一个整数 n（1 <= n <= 100），接下来的一行包含 n 个整数 ai（1 <= ai <= 100）。
 *
 *
 * 输出描述:
 * 输出一行表示最少需要移动多少次可以平分苹果，如果方案不存在则输出 -1。
 * 示例1
 * 输入
 * 4
 * 7 15 9 5
 * 输出
 * 3
 */
public class DivideApples {

    // 思路：先算总和记平均值，如果除不尽，返回-1，
    // 如果平均值为奇数但是数组里有偶数，返回-1，如果数组里有奇数，平均值为偶数返回-1；
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int num = scanner.nextInt();

        int[] arr = new int[num];

        for (int i = 0; i < num; i++) {
            arr[i] = scanner.nextInt();
        }

        System.out.println(divideApples(arr));

    }

    private static int divideApples(int[] arr) {

        if (arr.length == 0) {
            return -1;
        }

        if (arr.length == 1) {
            return 0;
        }

        int sum = 0; // 苹果总数
        int sin = 0; // 奇数总数
        int dou = 0; // 偶数总数

        for (int i = 0; i < arr.length; i++) {
            if (arr[i]%2 == 1) {
                sin++;
            } else {
                dou++;
            }
            sum+=arr[i];
        }

        if (sum%arr.length!=0) {
            return -1;
        }

        int average = sum/arr.length;
        if (average%2==0&&sin>0) {
            return -1;
        }
        if (average%2==1&&dou>0) {
            return -1;
        }
        int count = 0; // 转移次数

        Arrays.sort(arr);//先排序

        int i = arr.length - 1;
        int j = 0;

        while (i>j) {
            while (arr[i] > average && arr[j] < average) {
                arr[i]-=2;
                arr[j]+=2;
                count++;
            }
            if (arr[i]==average) {
                i--;
            }
            if (arr[j] == average) {
                j++;
            }
        }

        return count;
    }
}

/**
 * 题解思路：（我做了一些无用功）
 *
 * 链接：https://www.nowcoder.com/questionTerminal/a174820de48147d489f64103af152709?answerType=1&f=discussion
 * 来源：牛客网
 *
 * 解题思路：
 * 方案存在条件：
 * 1.苹果数必须全奇或全偶（因为你每次拿两个苹果不会改变苹果数的奇偶性质，但是最后要保证都变成为平均值，所以奇偶性必须相同）
 * 2.总苹果数必须能整除奶牛只数，即平均数必须为整数
 * 所以其他情况都返回-1
 * 当满足前面两个条件后，我们只需要遍历数组，计算每个苹果数和平均值的差值，然后相加起来得到的答案res,再除以4即为移动次数（这里为啥除以4，是因为我们的res中是有取出和放入的，所以操作的苹果数只有 res/2 个，然后我们每次操作是2个苹果，所以移动次数为 res/4 )
 */
//public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNextInt()){
//        int n = sc.nextInt();
//        int[] nums = new int[n];
//        int sum = 0;
//        int odd = 0;
//        for(int i = 0;i<nums.length;i++){
//        nums[i] = sc.nextInt();
//        if(nums[i]%2!=0){
//        if(odd==-1){
//        System.out.println(-1);
//        return;
//        }
//        odd = 1;
//        }else{
//        if(odd==1){
//        System.out.println(-1);
//        return;
//        }
//        odd = -1;
//        }
//        sum+=nums[i];
//        }
//        if(sum%n!=0){
//        System.out.println(-1);
//        return;
//        }
//        int avg = sum/n;
//        int count = 0;
//        for(int i = 0;i<nums.length;i++){
//        if(nums[i]!=avg){
//        count+=Math.abs(nums[i]-avg);
//        }
//        }
//        System.out.println(count/4);
//        }
//        }